package com.example.array;

import java.util.Deque;
import java.util.LinkedList;

public class Leetcode921_MinAddToMakeValid {
    public static void main(String[] args) {

        System.out.println(minAddToMakeValid("())"));

    }

    /**
     * 遍历整个字符串
     * 遇到'('就将其压入栈中
     * 遇到')'并且栈不为空则将栈顶出栈
     *        栈为空时将添加的括号数+1
     * 当遍历完了整个字符串后
     * 将栈中所有元素依次出栈并将添加的括号数+1
     *
     * @param s
     * @return
     */
    public static int minAddToMakeValid(String s) {
        int result = 0;
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(')
                stack.push(c);

            if (c == ')') {
                if (stack.isEmpty())
                    result++;

                if(!stack.isEmpty())
                    stack.pop();
            }
        }

        while (!stack.isEmpty()) {
            stack.pop();
            result++;
        }
        return result;
    }
}
